# 你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子
# 列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。 
# 
#  给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表
# 中的 curr 之后 和 curr.next 之前 。 
# 
#  返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  
# 输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
# 输出：[1,2,3,7,8,11,12,9,10,4,5,6]
# 解释：输入的多级列表如上图所示。
# 扁平化后的链表如下图：
# 
#  
# 
#  示例 2： 
# 
#  
# 
#  
# 输入：head = [1,2,null,3]
# 输出：[1,3,2]
# 解释：输入的多级列表如上图所示。
# 扁平化后的链表如下图：
# 
#  
# 
#  示例 3： 
# 
#  
# 输入：head = []
# 输出：[]
# 说明：输入中可能存在空列表。
#  
# 
#  
# 
#  提示： 
# 
#  
#  节点数目不超过 1000 
#  1 <= Node.val <= 10⁵ 
#  
# 
#  
# 
#  如何表示测试用例中的多级链表？ 
# 
#  以 示例 1 为例： 
# 
#  
#  1---2---3---4---5---6--NULL
#          |
#          7---8---9---10--NULL
#              |
#              11--12--NULL 
# 
#  序列化其中的每一级之后： 
# 
#  
# [1,2,3,4,5,6,null]
# [7,8,9,10,null]
# [11,12,null]
#  
# 
#  为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。 
# 
#  
# [1,2,3,4,5,6,null]
# [null,null,7,8,9,10,null]
# [null,11,12,null]
#  
# 
#  合并所有序列化结果，并去除末尾的 null 。 
# 
#  
# [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
#  
# 
#  
#  
# 
#  Related Topics 深度优先搜索 链表 双向链表 👍 438 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
from typing import Optional

from LeetCode.Test.LinkTool import DoubleListNode, DoubleLinkedListTool, Link

"""
思路：
递归：如果一个节点node有child分支就把它插入node和nextnode中间
dfs总是返回最链表的最后一个节点（没有下一个也没有child，则必然是最后一个）
"""


class Solution:

    def flatten(self, head: 'Optional[DoubleListNode]') -> 'Optional[DoubleListNode]':
        """
        # dfs 函数总是返回处理完的那段分支的最后一个珠子
        def dfs(cur):
            # 防止空链表报错
            if not cur:
                return None

            # 记录下一个节点，因为在连接节点的时候会用到
            next_node = cur.next
            # 如果有child
            if cur.child:
                # 把child连到结果链表中
                cur.next = cur.child
                cur.child.prev = cur

                # 检查是否还能向下衍生
                last = dfs(cur.child)
                # 当走出第一个递归时，代表某一个节点的全部child已经遍历完了，应当把最后一个child（last）和下一个遍历的节点连起来
                if next_node:
                    last.next = next_node
                    next_node.prev = last
                #分支已经连接到结果链表中了，此时child设置为空
                cur.child = None
                # 继续处理下一个节点，并返回最后一个节点
                if next_node:
                    return dfs(next_node)
                return last
            # 能够到这一步说明已经跳出一个递归，已经没有child了，或者本身就没有child。继续处理下一个节点
            if next_node:
                return dfs(next_node)
            # 如果既没有子节点也没有下一个节点，返回当前节点（分支的最后一个节点）
            return cur

        # 我们调用和方法dfs,但是没有使用它的返回值，这个方法的返回值是其组成链表的最后一个元素
        dfs(head)
        return head
        """

        def dfs(cur):
            if not cur:
                return None
            next_node = cur.next
            if cur.child:
                cur.next = cur.child
                cur.child.prve = cur

                last = dfs(cur.child)
                cur.child = None
                if next_node:
                    last.next = next_node
                    next_node.prve = last
                    return dfs(next_node)
                return last
            if next_node:
                return dfs(next_node)

            return cur
        dfs(head)
        return head


# leetcode submit region end(Prohibit modification and deletion)
head = DoubleLinkedListTool([1, 2, 3, 4, 5, 6])
two = DoubleLinkedListTool([7, 8, 9, 10])
three = DoubleLinkedListTool([11, 12])
head.next.next.child = two
two.next.child = three
Link.each(Solution().flatten(head))
